/*
 * OptimalSmallCover.cpp
 *
 *  Created on: 24 nov. 2011
 *  Authors: bnoleau, cybourdi, rlecrois
 */

#include "OptimalSmallCover.h"

using namespace std;

OptimalSmallCover::OptimalSmallCover(int size) {
	sizeCover = size;
}

OptimalSmallCover::~OptimalSmallCover() {
}

list<int> OptimalSmallCover::vertexCover(Graph* g) {
	list<int> cover;
	bool result = vertexCoverRecur(g, sizeCover, cover);
	
	if(!result)
		cover.clear();

	return cover;
}

bool OptimalSmallCover::vertexCoverRecur(Graph* g, int sizeCover, list<int> &cover){
	bool result = false;
	int p2 = sizeCover - 1;
	
	if(sizeCover > 0) {
		int i = 0;
		cover.push_back(g->nodeAt(0)->getID());
		while(( i < g->numberOfNode()) && (!result)) {
			cover.pop_back();
			cover.push_back(g->nodeAt(i)->getID());
			result = vertexCoverRecur(g, p2, cover);
			i++;
		}
		if(!result)
			cover.pop_back();
	}
	else {
		result = testCover(g, cover);
	}
	
	return result;
}

bool OptimalSmallCover::testCover(Graph* g, list<int> cover) {
	bool result = true;
	int i = 0;
	
	while(( i < g->numberOfNode()) && (result)) {
		Node* tmp = g->nodeAt(i);

		if(!includeInList(cover, tmp)) {
			list<Node*> *tmpEdges = tmp->getEdgeList();
			list<Node*>::iterator it = tmpEdges->begin() ;

			while((it != tmpEdges->end()) && (result)){
				result = result && includeInList(cover, (*it));
				it++;
			}
		}
		i++;
	}

	return result;
}

bool OptimalSmallCover::includeInList(list<int> listNodes, Node* n){
	bool result = false;
	list<int>::iterator it = listNodes.begin() ;
	
	while((it != listNodes.end()) && (!result)){
		result = ((*it) == n->getID());
		it++;
	}

	return result;
}

